// 164.最大间隔
package Leetcode_Second_Brush;

import java.util.Arrays;

public class Solution164 {
    public int maximumGap(int[] nums) {
        // 检查数组是否有足够的元素计算间隔
        if (nums == null || nums.length < 2) {
            return 0;
        }

        // 获取数组的最大值和最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (int n : nums) {
            max = Math.max(max, n);
            min = Math.min(min, n);
        }

        // 如果最大值和最小值相同，则间隔为0
        if (max == min) {
            return 0;
        }

        int length = nums.length;
        // 计算最大间隔的最小值
        int bucketSize = Math.max(1, (max - min) / (length - 1));

        // 计算桶的数量，每个桶维护一个最大值和最小值
        int bucketCount = (max - min) / bucketSize + 1;
        int[][] buckets = new int[bucketCount][2];
        for (int[] bucket : buckets) {
            bucket[0] = Integer.MAX_VALUE;
            bucket[1] = Integer.MIN_VALUE;
        }

        // 将数组中的每个数放入对应的桶中，并更新桶的最小值和最大值
        for (int n : nums) {
            int index = (n - min) / bucketSize;
            buckets[index][0] = Math.min(buckets[index][0], n);
            buckets[index][1] = Math.max(buckets[index][1], n);
        }

        // 计算桶之间的最大间隔
        int maxGap = 0;
        int previousMax = min; // 初始化为最小值

        for (int[] bucket : buckets) {
            // 跳过空桶
            if (bucket[0] == Integer.MAX_VALUE) {
                continue;
            }
            // 当前桶的最小值与上一个非空桶的最大值之间的差值
            maxGap = Math.max(maxGap, bucket[0] - previousMax);
            previousMax = bucket[1];
        }

        return maxGap;
    }
}

class Solution164_v2 {
    public int maximumGap(int[] nums) {
        if (nums.length <= 1)
            return 0;
        // 获取nums数组中的最大值
        int maxValue = Arrays.stream(nums).max().getAsInt();
        long exp = 1; // 表示取的个位，十位、百位等
        int[] buf = new int[nums.length]; // 每轮基数排序后的数组

        // 最大的位数不会超过数组的最大值
        while (exp <= maxValue) {
            int[] bucket = new int[10]; // 使用一个表示0~9个数字的桶存储每个位不同数字出现的次数
            for (int num : nums) {
                int digit = (num / (int) exp) % 10;
                bucket[digit]++; // 计数
            }

            // 计算前缀和，前缀和表示数字在最终排序数组的下标
            for (int i = 1; i < bucket.length; i++) {
                bucket[i] += bucket[i - 1];
            }

            // 填充排序数组buf
            // 从后往前遍历可以保证排序的稳定性
            for (int i = nums.length - 1; i >= 0; i--) {
                int digit = (nums[i] / (int) exp) % 10;
                int index = bucket[digit] - 1; // 该数字在最终排序数组的下标
                buf[index] = nums[i];
                bucket[digit]--; // 注意减一
            }

            System.arraycopy(buf, 0, nums, 0, nums.length);
            exp *= 10;
        }

        // 计算题目的解
        int result = 0;
        for (int i = 1; i < nums.length; i++) {
            result = Math.max(result, nums[i] - nums[i - 1]);
        }
        return result;
    }
}